package oj;

//剑指offer 35：复杂链表的复制：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
public class Solution_offer35_2 {
    public Node copyRandomList(Node head) {
        //方法二:将复制的结点直接放到老结点的后边，构成一条链表
        //建立老结点到新结点的映射关系：cur.next == node
        Node cur = head;
        while(cur != null){
            Node next = cur.next;
            //复制
            Node node = new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = next;
        }
        //从头开始再次遍历
        //修改 node.random 的关系
        //node.random = cur.random 映射到对应的新结点
        //node.random = cur.random.next;
        cur = head;
        while(cur != null){
            Node node = cur.next;
            if(cur.random != null){
                node.random = cur.random.next;
            }else{
                node.random = null;
            }
            cur = node.next;
        }
        //不断一组一组地遍历，使用尾插的方式，将老结点和新结点尾插到合适的链表中
        Node oldHead = new Node(-1);
        Node oldLast = oldHead;
        Node newHead = new Node(-1);
        Node newLast = newHead;

        cur = head;
        while(cur != null){
            Node node = cur.next;       //这一组的新结点
            Node next = node.next;      //记录下一个老结点的位置
            //把 cur 尾插到 oldHead + oldLast 对应的链表中
            oldLast.next = cur;
            oldLast = cur;
            cur.next = null;
            //把 node 尾插到 newHead + newLast 对应的链表中
            newLast.next = node;
            newLast = node;
            node.next = null;

            cur = next;
        }
        return newHead.next;
    }
}
